解题思路

贪心要超时，所以我们继续用动态规划来做此题； 首先我们思考一下当我们有一个长度为 L 的磁带时，我们需要哪些信息？

1. 储存的程序个数；

2. 它们占用的磁带长度； 所以我们要在一个元素位置显示两个数据，因此我们采用结构体来显示； 并且题目要求将在磁带上的每个程序的长度都原顺序的输出

   • dp[ i ].count 表示磁带长度为 i 最多可以存的程序的个数
   • dp[ i ].sumVs 表示磁带长度为 i 最多可以占用的磁带长度
   • dp[ i ].army 表示存了每个程序的顺序（倒叙）

现在我们思考一下，什么时候更新数据？

1. 当放入程序数更多的时候更新：dp[ j ].count < dp[ j - s ].count + 1
2. 当程序数相同占用磁带的长度更长时更新：dp[ j ].count == dp[ j - s ].count + 1 && dp[ j ].sumVa <= dp[ j - s ].sumVa + s 因为结果要最小的字典序答案，所以我们的动态更新需要从后往前更新；

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define LL long long int
using namespace std;

struct node
{
    int count;
    int sumVa;
    vector<LL> army;

    //构造函数：初始化列表-->node():count(0),sumVa(0){};
    node() {
        count = 0;
        sumVa = 0;
        army.clear();
    }
};

int main()
{
    int n, Length;
    while (cin >> n >> Length)
    {
        int len[605];
        for (int i = 1; i <= n; i++)
            cin >> len[i];

        node dp[6005];            //必须写在main()
                        //题目巨坑：输出最小字典序的程序
        for (int i = n; i >0; i--)    //只有也必须倒叙规划
        {
            int s = len[i];
            for (int j = Length; j >= 0; j--)
            {
                if (j >= s)
                {
                    if (dp[j].count < dp[j - s].count + 1
                        || dp[j].count == dp[j - s].count + 1
                        && dp[j].sumVa <= dp[j - s].sumVa + s)
                    {
                        dp[j].count = dp[j - s].count + 1;
                        dp[j].sumVa = dp[j - s].sumVa + s;
                        dp[j].army  = dp[j - s].army;
                        dp[j].army.push_back(s);
                    }
                }
            }
        }

        cout << dp[Length].count << " " << dp[Length].sumVa << endl;
        for (int i = dp[Length].army.size() - 1; i >= 0; i--)
        {
            if (i != dp[Length].army.size() - 1)
                cout << " ";
            cout << dp[Length].army[i];
        }
        cout << endl;
    }
    return 0;
}